/* 
 * File:   vertch_rec.h
 * Author: boyan
 *
 * Created on June 4, 2009, 11:11 AM
 */

#ifndef _VERTCH_REC_H
#define	_VERTCH_REC_H

#ifndef _in_VERTCHIMPL_CC_
#error "must not include " __FILE__ " directly. include VertChImpl.h instead"
#endif

/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
 * VertCh_rec is an abstract class that makes a list of all elements that    *
 * all of their nodes are pending.  It also provides the gory machinary      *
 * for the recursion algorithm for selecting nodes.                          *
 *%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/

enum CheckResult
{
    check_failed = -1,
    check_fine = 0, // this is an odd one.  indicates "none of the others"
    check_change = 1, // only check_edges can return check_done
    check_done = 2 // it means that no edges are crossed
};

template <unsigned short DIM>
class VertCh_rec : public VertCh_base
{
public:
    void dump_pending_elems(std::ostream &S = std::cout) const;

    virtual bool support_dimension(int dim) const
    {
        return dim == DIM;
    }

protected:
    virtual void init();
    virtual void done();

    virtual bool choose();
    virtual bool recursion(size_t idx, int node, int level);

    signed short mSignToMark; // must be 1 or -1

    virtual void sort_pending_nodes()
    {
        if (mSignToMark == -1)
        {
            // sort pending nodes by distance (closest last)
            std::sort(PN.begin(), PN.end(), PendingNode::compare_distance_inc);
            std::reverse(PN.begin(), PN.end());
        }
        else /* if (mSignToMark == 1) */
        {
            // sort pending nodes by connectivity (most connected first)
            std::sort(PN.begin(), PN.end(), PendingNode::compare_connectivity_dec);
        }
    }

    virtual bool skip_node(size_t idx, int node, int level)
    {
        if (mSignToMark == 1 && vert_NCE[node] == 0)
            return true;
        return false;
    }

    inline void mark_node(int node, int level)
    {
        set_node_code(node, mSignToMark * level);
    }

    inline void unmark_node(int node, int level)
    {
        set_node_code(node, -mSignToMark * level);
    }

    typedef fixed_size_vector_with_int_codes<size_t, DIM + 1 > PendingElem;
    std::vector<PendingElem> PT; // the elements with DIM+1 pending nodes

    void set_node_code(size_t node, int code);
    void cleanup_level(int level);


    CheckResult check_PT(const PendingElem &PT, int &node); // check one
    CheckResult check_elems(int level); // check all
    CheckResult check_CE(const CrossedEdge &CE, int &node); // check one
    CheckResult check_edges(int level); // check all


    //======================================================================
    // some utility functions ==============================================

    inline bool is_elem_pending(const size_t *nds) const
    {
        for (const size_t *end = nds + DIM + 1; nds < end; nds++)
            if (!is_node_pending(*nds))
                return false;
        return true;
    }
};


/*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
 *                      Implementation of VertCh_rec                         *
 *%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*/

//////////////////////////////////////////////////////////////////////////////
//  output for debugging

template <unsigned short DIM>
void VertCh_rec<DIM>::dump_pending_elems(std::ostream &S) const
{
    S << "Pending elems are : " << std::endl;
    for (size_t i = 0; i < PT.size(); i++)
    {
        S << std::setw(4) << i << " :";
        for (size_t j = 0; j < DIM; ++j)
            S << std::setw(4) << PT[i].values[j] << ", ";
        S << std::setw(4) << PT[i].values[DIM] << " :\t";
        for (size_t j = 0; j < DIM; ++j)
            S << std::setw(4) << PT[i].codes[j] << ", ";
        S << std::setw(4) << PT[i].codes[DIM] << std::endl;
    }
}

/////////////////////////////////////////////////////////////////////////////
//  init() and done()

template <unsigned short DIM>
void VertCh_rec<DIM>::init()
{
    this->VertCh_base::init(); // call the parent's init()

    // count elements with (DIM+1) pending nodes
    int NPT = 0;
    for (size_t el = 0; el < global_patch.num_elements(); el++)
    {
        Mesquite::MsqMeshEntity &T = global_patch.element_by_index(el);
        if (this->is_elem_pending(T.get_vertex_index_array()))
            NPT++;
    }
    // populte PT
    PT.reserve(NPT);
    for (size_t el = 0; el < global_patch.num_elements(); el++)
    {
        Mesquite::MsqMeshEntity &T = global_patch.element_by_index(el);
        size_t *el_nds = T.get_vertex_index_array();
        if (this->is_elem_pending(el_nds))
            PT.push_back(el_nds);
    }

}

template <unsigned short DIM>
void VertCh_rec<DIM>::done()
{
    PT.clear();
    this->VertCh_base::done();
}

/////////////////////////////////////////////////////////////////////////////
//  The gory stuff

template <unsigned short DIM>
void VertCh_rec<DIM>::set_node_code(size_t node, int code)
{
#if defined(PRINTSTUFF) && PRINTSTUFF && 0
    std::cout << "set_node_code(" << node << "," << code << ")" << std::endl;
#endif
    // mark the pending node
    for (size_t i = 0; i < PN.size(); ++i)
        if (PN[i].node == node)
        {
            PN[i].code = code;
            break;
        }

    // mark the PT
    for (size_t i = 0; i < PT.size(); ++i)
        PT[i].set_value_code(node, code);

    // mark the CE
    if (code <= 0)
        for (size_t i = 0; i < CE.size(); i++)
            CE[i].set_value_code(node, code);
    else
    {
        // if we are setting a positive code, we need to update the
        // number of crossed edges per node.  An edge with positive code
        // is no longer crossed
        vert_NCE[node] = 0;
        for (size_t i = 0; i < CE.size(); i++)
        {
            size_t j = CE[i].set_value_code(node, code);
            if ((j < 2) && (CE[i].get_idx_code(1 - j) <= 0))
                --vert_NCE[i];
        }
        for (size_t idx = 0; idx < PN.size(); idx++)
            PN[idx].NCE = vert_NCE[PN[idx].node];
    }
}

template <unsigned short DIM>
void VertCh_rec<DIM>::cleanup_level(int level)
{
    for (size_t idx = 0; idx < PN.size(); ++idx)
    {
        if (abs(PN[idx].code) >= level)
            this->set_node_code(PN[idx].node, 0);
    }
    // update the vert_NCE array
    for (size_t idx = 0; idx < vert_NCE.size(); ++idx)
        vert_NCE[idx] = 0;
    for (size_t idx = 0; idx < CE.size(); ++idx)
    {
        if (CE[idx].codes[0] == 0 && CE[idx].codes[1] <= 0)
            ++vert_NCE[CE[idx].codes[0]];
        if (CE[idx].codes[0] <= 0 && CE[idx].codes[1] == 0)
            ++vert_NCE[CE[idx].codes[1]];
    }
    for (size_t idx = 0; idx < PN.size(); idx++)
        PN[idx].NCE = vert_NCE[PN[idx].node];

}

/////////////////////////////////////////////////////////////////////////////
// The checking of the edges stuff

template <unsigned short DIM>
CheckResult VertCh_rec<DIM>::check_CE(const CrossedEdge& CE, int& node)
{
    if (CE.codes[0] > 0 || CE.codes[1] > 0)
        return check_done;
    // now neither code is positive
    if (CE.codes[0] < 0 && CE.codes[1] < 0)
        return check_failed;
    // now at least one code is 0 and the other is 0 or negative;
    if (CE.codes[0] < 0)
        node = CE.values[1]; // codes[1] == 0
    else if (CE.codes[1] < 0)
        node = CE.values[0]; // codes[0] == 0
    else
        return check_fine; // both codes are 0
    return check_change;
}

template <unsigned short DIM>
CheckResult VertCh_rec<DIM>::check_edges(int level)
{
    bool change = false;
    size_t done = 0;
    int node;
    for (size_t idx = 0; idx < CE.size(); idx++)
    {
        switch (check_CE(CE[idx], node))
        {
        case check_failed:
            return check_failed;
        case check_fine:
            break;
        case check_change:
            change = true;
            set_node_code(node, level);
            break;
        case check_done:
            ++done;
            break;
        }
    }
    // if edge failed we return immediately.  if we are here no edge failed.
    // it may happen that after something changed all edges are done.
    // in this case we have to check the elements before we conclude
    // that we are done.  In other words, we are done when all edges are done
    // and nothing changed.
    if (change)
        return check_change;
    if (done == CE.size())
        return check_done;
    // no one changed, no one failed, not all are done, so we are just fine!
    return check_fine;
}

/////////////////////////////////////////////////////////////////////////////
// The checking of the elems stuff

template <unsigned short DIM>
CheckResult VertCh_rec<DIM>::check_PT(const PendingElem& aPT, int& node)
{
    size_t p_num = 0; // number of positive codes
    size_t z_idx = -1; // index of zero code (if any)
    for (size_t j = 0; j < DIM + 1; j++)
    {
        if (aPT.codes[j] < 0)
            return check_fine; // negative code means the element is fine
        if (aPT.codes[j] == 0)
            z_idx = j;
        else
            ++p_num;
    }
    assert(p_num <= DIM + 1);
    switch (p_num)
    {
    case DIM + 1 : // all codes are positive
        return check_failed;
    case DIM: // DIM positive codes and the remaining one is 0
        node = aPT.values[z_idx]; // we have to set the 0 code to -level
        return check_change;
    default: // all codes are >=0 with more than one 0
        return check_fine;
    }
    // we will never get here, but compiler complains without next line
    return check_failed;
}

template <unsigned short DIM>
CheckResult VertCh_rec<DIM>::check_elems(int level)
{
    bool change = false;
    int node;
    for (size_t idx = 0; idx < PT.size(); idx++)
    {
        switch (check_PT(PT[idx], node))
        {
        case check_failed:
            return check_failed;
        case check_fine:
            break;
        case check_change:
            change = true;
            set_node_code(node, -level);
            break;
        case check_done: //this will never be returned
            break;
        }
    }
    if (change)
        return check_change;
    else
        return check_fine;
}

/////////////////////////////////////////////////////////////////////////////
// Implementation of choose() and recursion()

template <unsigned short DIM>
bool VertCh_rec<DIM>::choose()
{
#if defined(PRINTSTUFF) && PRINTSTUFF
    dump_pending_nodes();
#endif
    assert(mSignToMark == 1 || mSignToMark == -1);
    sort_pending_nodes();

    Mesquite::Mesh::VertexHandle *h = global_patch.get_vertex_handles_array();
    // mark nodes that should not be moved at level -1
    for (size_t i = 0; i < PN.size(); i++)
    {
        size_t index = PN[i].node;
        Mesquite::MsqVertex &node = global_patch.vertex_by_index(index);
        if (!node.is_free_vertex())
            set_node_code(index, -1);
        if ((*levelset_codes)[h[index]] == ls_onsurf)
            set_node_code(index, 1);
    }
    bool changed;
    do
    {
        changed = false;
        CheckResult ret = this->check_edges(1);
        if (ret == check_failed)
            return false;
        if (ret == check_done)
            return true;
        if (ret == check_change)
            changed = true;
        ret = check_elems(1);
        if (ret == check_failed)
            return false;
        if (ret == check_change)
            changed = true;
    }
    while (changed);

#if defined(PRINTSTUFF) && PRINTSTUFF 
    dump_pending_nodes();
    dump_crossed_edges();
    dump_four_node_elems();
#endif
    // loop over pending nodes and try them out one by one
    for (size_t idx = 0; idx < PN.size(); idx++)
    {
        if (PN[idx].code != 0)
            continue;
        if (this->recursion(idx, PN[idx].node, 2))
            return true;
        unmark_node(PN[idx].node, 1);
    }
    return false;
}

template <unsigned short DIM>
bool VertCh_rec<DIM>::recursion(size_t idx, int node, int level)
// NOTE: level is always positive.  It indicates the current depth of the
// recursion.  Nodes are marked with
//      code = level to indicate "chosen", or
//      code = -level to indicate "not chosen"
// All nodes are initialized with code = 0 indicating not handled.  If a node
// still has code = 0 after recursion is done, this means "not chosen"
{
#if defined(PRINTSTUFF) && PRINTSTUFF
    std::cout << "recursion_edges(" << idx << "," << node << "," << level
            << ")" << std::endl;
#endif

    if (skip_node(idx, node, level))
        return false;

    // mark node as "chosen"
    mark_node(node, level);

    bool change = true;
    while (change)
    {
        change = false;
        switch (check_edges(level))
        {
        case check_failed:
#if defined(PRINTSTUFF) && PRINTSTUFF && 0
            std::cout << "check_edges failed" << std::endl;
#endif
            cleanup_level(level);
            return false;
        case check_fine:
            break;
        case check_done:
            return true;
        case check_change:
            change = true;
        }
        switch (check_elems(level))
        {
        case check_failed:
#if defined(PRINTSTUFF) && PRINTSTUFF && 0
            std::cout << "check_elems failed" << std::endl;
#endif
            cleanup_level(level);
            return false;
        case check_change:
            change = true;
            break;
        default:
            ; // this is not possible
        }
        if (change)
            continue;
#if defined(PRINTSTUFF) && PRINTSTUFF && 00
        dump_pending_nodes();
        dump_crossed_edges();
        dump_four_node_elems();
#endif

        for (; idx < PN.size(); idx++)
        {
            if (PN[idx].code != 0)
                continue;
            if (recursion(idx, PN[idx].node, level + 1))
                return true;
            unmark_node(PN[idx].node, level);
            change = true;
            break;
        }
    }
    return false;
}


#endif	/* _VERTCH_REC_H */

